A Viterbi decoder can be used in convolutional decoding, and is widely used in communication systems. The Viterbi decoder employs the method of searching for the maximum likelihood sequence and calculating the minimum path metric to accomplish the error correction. The recent wireless communication products all utilize the Viterbi decoder. However, without the external power source, the wireless communication products can only be used for a limited duration as the power consumption is relatively high for the battery-powered products. Therefore, the criterion of low power consumption is important for the design of wireless communication products.
The Viterbi decoder is the module that consumes much power in the wireless communication products. The conventional Viterbi decoder uses the following two approaches: register exchange approach and traceback approach.
FIG. 1 shows the register exchange approach used in a conventional Viterbi decoder. As shown in FIG. 1, this approach stores the decoded bits of the survivor path of the current state into the register when an input signal arrives. The subsequent arrival of an input signal requires the duplication of previously decoded bits and writing the current decoded bits into the register. Therefore, the bits stored in the register will increase as the input signal increases. The register exchange approach eliminates the time and the power consumption of the traceback because the value stored in the register is the decoded bit sequence when the last input signal arrives. However, the duplication of the decoded bits of the previous stage to the next stage requires high power consumption and a large memory area; therefore, this approach can only be used in low complexity and high throughput systems.
FIG. 2 shows the traceback approach of a conventional Viterbi decoder. As shown in FIG. 2, the traceback approach records the survivor branch of each state. For the Viterbi decoder with a total of four states, it requires two bits to record the survivor branch of the state and stores into the path memory. It can even use only one bit to record whether it is the upper branch or the lower branch. On traceback, by reading the path memory, with table look-up, the decoded bits can be obtained. Because this approach requires less power and smaller memory area, the traceback approach is suitable for high complexity systems.
FIG. 3 shows a conventional three-pointer even method of memory management. The memory management method is applicable to the implementation of the traceback approach. By dividing the memory into a plurality of memory blocks, this method allows the parallel execution of the reading and writing to the memory. However, this method has an utilization rate of 4/6 for the memory; that is, four out of the allocated six blocks must be in use simultaneously. As the memory access uses about 80% of the power consumption, it is important to reduce the memory access and shut down the power to the memory block when the block is not in use so that the overall power consumption can be reduced.
The conventional Viterbi decoder utilizes path memory to store each stage and the survivor branch of each stage. The traceback starts when the depth of the stored stages reaches about 5-6 times of the constraint length. During the traceback, the state of last stage having the minimum path metric is first found, and then the survivor path in the path memory is read to compute the state of the previous stage in the survivor path. This process must be done stage by stage, and the path memory must be accessed in each stage. Until traceback is at the end of the survivor path, the decoded bits can be obtained. Because the number of memory accesses is large, the power consumption of this method is also large.
FIG. 4 shows the relationship between the bit error rate (BER) and the path overlapping. A conventional prediction method utilizes the relationship between the BER and the path overlapping. When the input signal of the Viterbi decoder has a BER less than 3.7×10−2, the probability of the overlapping of the traceback path and the survivor path in the first three stages is higher than 97%. There are two important issues in this relationship. First, in a low BER system, the probability that the previous traceback path overlaps the current traceback path is high. If the information of the previous traceback path can be stored, the remaining traceback can be saved when the paths overlap. This also saves the power used in path memory access. Second, the survivor branch is recorded whenever an input signal arrives. If each stage computes the state of the minimum path metric, and determines the legitimacy of the state in the survivor path based on whether a connection exists between this state and the state of the minimum path metric of the previous stage, under the low BER condition, there will be a high probability that the survivor path will consist of the states of the minimum path metric of each stage.
In this conventional prediction method, six corresponding state buffers are used in addition to the six path memories of a conventional Viterbi decoder. The state buffers record the state sequence of the previous traceback path and the most likely correct state sequence predicted by the prediction mechanism. When the predicted minimum states are connected, the state of the minimum path metric in the previous stage is recorded in the state buffer. During the traceback, if the traceback path overlaps the path in the state buffer, the connected state stored in the state buffer can be directly used to obtain the decoded bits. Thus, no further path memory access is required for the decoding. When the channel condition is good, that is, the path prediction mechanism is correct, 75% of memory access is saved in comparison to the traceback approach of the conventional Viterbi decoder. The power consumption is greatly reduced.
Take the structure of the conventional three-pointer even method as an example. There are four memory blocks operating simultaneously in the Viterbi decoder using a traceback approach. The conventional prediction method, when the path prediction mechanism is completely correct, writes the state of the minimum path metric of the previous stage into only one memory block, When the channel condition is good, that is, the path prediction mechanism is correct, it still requires to use the traceback to observe the connected relationship to obtain the decoded bits.
For wireless communication products, the power consumption criterion is more restrictive because of the mobility. Although the traceback approach uses less power and less memory area than the register exchange approach, and is already widely used, it is still a challenge to further lower the power consumption.